# -*- coding: utf-8 -*-
# author yzs
# date 2019-03-04
'''
数组查询
Description
Given an array, the task is to complete the function which finds the maximum sum subarray,
where you may remove atmost one element to get the maximum sum.
Input
第一行为测试用例个数T；后面每两行表示一个用例，第一行为用例中数组长度N，第二行为数组具体内容。
Output
每一行表示对应用例的结果。
Sample Input 1 
1
5
1 2 3 -4 5
Sample Output 1
11
Hint
例如，对一个数组A[] = {1, 2, 3, -4, 5}，要移除-4得到最大和的子数组，和为11.
'''


def max_sum_subarray(arr, n):
    A = [0 for k in range(n)]
    B = [0 for k in range(n)]

    max_now, max_then = arr[0], arr[0]
    for i in range(1,n):
        max_now = max(arr[i], max_now + arr[i])
        max_then = max(max_then, max_now)
        A[i] = max_now
    max_now = max_then = B[n - 1] = arr[n - 1]
    i = n - 2
    while i >= 0:
        max_now = max(arr[i], max_now + arr[i])
        max_then = max(max_then, max_now)
        B[i] = max_now
        i -= 1
    max_final = max_then
    for i in range(1, n - 1):
        max_final = max(max_final, A[i - 1] + B[i + 1])
    return max_final


t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    datas = list(map(int, input().strip().split()))[:n]
    print(max_sum_subarray(datas, n))
